package com.zhzh.sc.demo.leetcode.learn.link;

public class CircleList {


    //Definition for singly-linked list.
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }


    /**
     * https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1212
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        ListNode walker = head;
        ListNode runner = head;
        while (runner.next != null && runner.next.next != null) {
            walker = walker.next;
            runner = runner.next.next;
            if (walker == runner) return true;
        }
        return false;
    }

    /**
     * https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1214
     *
     * @param head
     * @return
     */
    public ListNode getCycleStartIndex(ListNode head) {
        if (head == null)
            return null;
        ListNode walker = head;
        ListNode runner = head;
        while (runner.next != null && runner.next.next != null) {
            walker = walker.next;
            runner = runner.next.next;
            if (walker == runner) {
                while (head != walker) {
                    head = head.next;
                    walker = walker.next;
                }
                return walker;
            }
        }
        return null;
    }

}
